// main

//解决一个警察抓贼的问题，警察先走，能否抓到贼
/*
			(4)
		/  	 |		\
	   /	 |		 \
	(3)		(0)警察	 (5)贼
	  \		/\		/
	   \   /  \   /
		(2)---(1)
		警察在0位置处，警察先走，能否抓到贼，本代码是解决这个问题而实现，可以调回合数以便获得警察用最少步数抓到贼

*/
package main

import (
	"fmt"
)

type node struct {
	top    *node
	left   *node
	right  *node
	bottom *node
	index  int
}

func goTop(tmp *node) *node {
	return tmp.top
}
func goBottom(tmp *node) *node {
	return tmp.bottom
}
func goRight(tmp *node) *node {
	return tmp.right
}
func goLeft(tmp *node) *node {
	return tmp.left
}

/*
func Catch(polic *node, thief *node) bool {
	tmp := goTop(polic)
	if tmp != nil {
		if tmp == thief {
			fmt.Println("polic index", polic.index)
			return true
		} else {
			newThief := Escape(tmp, thief)
			res := Catch(tmp, newThief)
			if res {
				fmt.Println("polic index", tmp.index)
				return true
			}
		}
	}
}
func exist(record []int, index int) bool {
	for i := 0; i < len(record); i++ {
		if index == record[i] {
			return true
		}
	}
	return false
}
*/

//记录六个回合，每个回合遍历递归上下左右4个点，然后总回合数超过6个，回滚到上一层，只到查询到成功为止
func CatchWithStep(polic *node, thief *node, round int) bool {
	var tmp *node

	tmp = goTop(polic)
	if CatchSingleRound(tmp, thief, round) {
		fmt.Println("round:", round, "index", polic.index, "new indx", tmp.index, "thief index:", thief.index, "goTop")
		return true
	}
	tmp = goRight(polic)
	if CatchSingleRound(tmp, thief, round) {
		fmt.Println("round:", round, "index", polic.index, "new indx", tmp.index, "thief index:", thief.index, "goRight")
		return true
	}

	tmp = goLeft(polic)
	if CatchSingleRound(tmp, thief, round) {
		fmt.Println("round:", round, "index", polic.index, "new indx", tmp.index, "thief index:", thief.index, "goLeft")
		return true
	}
	tmp = goBottom(polic)
	if CatchSingleRound(tmp, thief, round) {
		fmt.Println("round:", round, "index", polic.index, "new indx", tmp.index, "thief index:", thief.index, "goBottom")
		return true
	}
	return false
}

//单回合警察操作
//如果抓到直接返回，不然继续递归调用最多6蹭
func CatchSingleRound(polic *node, thief *node, round int) bool {
	if polic == nil {
		return false
	}
	if polic == thief {
		return true
	}
	if round >= 3 {
		return false
	}
	//贼行动
	tmp := Escape(polic, thief)
	if tmp == nil {
		return true
	}
	round += 1

	return CatchWithStep(polic, tmp, round)
}

//逃跑
func GoEscap(polic *node, thief *node, step int) (bool, *node) {
	if thief == nil {
		return false, nil
	}
	if polic == thief {
		return false, nil
	}
	if step > 1 {
		return true, nil
	}
	if step > 0 && (polic == thief.top || polic == thief.bottom || polic == thief.left || polic == thief.right) {
		return false, nil
	}

	step += 1
	var tmp *node
	tmp = goTop(thief)
	if ok, _ := GoEscap(polic, tmp, step); ok {
		return true, tmp
	}
	tmp = goBottom(thief)
	if ok, _ := GoEscap(polic, tmp, step); ok {
		return true, tmp
	}
	tmp = goRight(thief)
	if ok, _ := GoEscap(polic, tmp, step); ok {
		return true, tmp
	}
	tmp = goLeft(thief)

	if ok, _ := GoEscap(polic, tmp, step); ok {
		return true, tmp
	}
	return false, nil
}

//贼逃跑这个是难点，还有回合处理也是难点
func Escape(polic *node, thief *node) *node {
	//贼行动多判断下一个回合会不会遇到警察
	_, tmp := GoEscap(polic, thief, 0)
	return tmp
}

func main() {
	var head *node = &node{index: 0}
	var rightBottom *node = &node{top: head, index: 1}
	head.right = rightBottom
	var leftBottom *node = &node{top: head, right: rightBottom, index: 2}
	head.left = leftBottom
	rightBottom.left = leftBottom
	leftBottom.right = rightBottom
	var left *node = &node{bottom: leftBottom, index: 3}
	leftBottom.left = left
	var top *node = &node{bottom: head, left: left, index: 4}
	head.top = top
	var right *node = &node{bottom: rightBottom, top: top, index: 5}
	top.right = right
	rightBottom.right = right

	round := 0
	if CatchWithStep(head, right, round) {
		fmt.Println("catch")
	} else {
		fmt.Println("No")
	}

	//tmp := goBottom(rightBottom)
	fmt.Println(rightBottom.index)
}
